/*
 * hashtable.c
 *
 *  Created on: 2020年12月22日
 *      Author: Administrator
 */

#include <stdio.h>
#include <stdlib.h>
#include "../../include/hash/hashtable.h"

void init_hash_table(HashTable* ht) {

	if (ht == NULL) return;

	for (int i = 0; i < SIZE; ++i) {
		ht->table[i] = 0;
	}
}

int hash(KeyType key) {

	int result = key % SIZE;
	return result;
}

void create_hash_table(HashTable* ht, int length, int* array) {

	int addr;
	for (int i = 0; i < length; ++i) {

		addr = hash(array[i]);

		if (ht->table[addr] == 0) {
			ht->table[addr] = array[i];
			printf("已存储，%d:%d\n", addr, array[i]);
		} else {
			int next_addr = linear_probing(ht, addr);
			ht->table[next_addr] = array[i];
			printf("已存储，%d:%d\n", next_addr, array[i]);
		}
	}
}

int linear_probing(HashTable* ht, int addr) {

	int next_addr = -1;
	for (int i = 0; i < SIZE-addr; ++i) {
		next_addr = hash(addr+i);

		if (ht->table[next_addr] == 0) // 找到可存储的位置
			return next_addr;
	}
	printf("线性探索失败！\n");
	return next_addr;
}

int search_hash_table(HashTable* ht, KeyType key) {

	int addr = hash(key);

	if (ht->table[addr] == key) return addr;
	else {
		for (int i = 1; i < SIZE-addr; ++i) {
			// 线性探测找下一个地址
			int next_addr = (addr+i) % SIZE;
			// 如果没有元素，则结束
			if (ht->table[next_addr] ==0)
				break;
			else if (ht->table[next_addr] == key) // 找到
				return next_addr;
			else
				continue;
		}
	}
	return -1;
}

void print_hash_table(HashTable* ht) {

	for (int i = 0; i < SIZE; ++i) {
		printf("%d ", ht->table[i]);
	}
	printf("\n");
}
